#include "abb.h"
#include <string.h>
#include <err.h>
#include <stdlib.h>

#include "data.h"
#include "key.h"
#include "bool.h"


struct sabb{
  struct sabb *left;
  struct sabb *rgt;
  struct sabb *f;
  key pal;
  data def;
};
/*
  abb
  abb_max(abb ar)
  {
  abb tem;
  if (!abb_is_empty(ar))
  {
  tem=ar;
  if( !abb_is_empty(tem->rgt) )
  while(!abb_is_empty(tem->rgt->rgt))
  tem=tem->rgt;
  }
  return tem;
  }*/
/*
  Si tiene hijo derecho,
  devuelve un arbol cuyo hijo derecho tiene el
  maximo del arbol tomado como argumento.
  Sino devuelve el mismo arbol.
*/

abb
abb_create(void)
{
  abb arbol;

  arbol=NULL;

  return(arbol);
}
/*
  Devuelve un arbol vacio.
  Cuando inserte vamos a tener que verificar si es vacio o no:
  si es vacio, aloca el nuevo y lo inserta de pecho,
  si no es vacio, aloca y coloca donde corresponda al nuevo nodo arboreo
*/

abb
abb_right(abb ar)
{
  abb der=NULL;

  if( !(abb_is_empty(ar)) )
    {
      der=ar->rgt;
      /*      return der;*/
    }
  else
    {
      warnx("El arbol es vacio\n");
    }
  return(der);
}
/*
  Devuelve el subarbol derecho del arbol que se le
  pase como argumento.

  PRE: !abb_is_empty(ar)
  POS: Cardamomo
*/

abb
abb_left(abb ar)
{
  abb izq=NULL;

  if(!abb_is_empty(ar))
    {
      izq=ar->left;
      /*      return izq;*/
    }
  else
    {
      warnx("El arbol es vacio\n");
    }
  return(izq);
}
/*
  Devuelve el subarbol izquierdo del arbol que se le
  pase como argumento.

  PRE: !abb_is_empty(ar)
  POS: Cardamomo
*/

key
abb_root_key(abb ar)
{
  key k;
  /*	k=key_empty();*/

  if(!abb_is_empty(ar))
    {
      k=ar->pal;
      /*      return k;*/
    }
  else
    {
      warnx("El arbol es vacio\n");
    }
  return(k);
}
/*
  Devuelve el key de la raiz del arbol que se le
  pase como argumento.

  PRE: !abb_is_empty(ar)
  POS: Cardamomo
*/



data
abb_root_data(abb ar)
{
  data d;

  if(!abb_is_empty(ar))
    {
      d=ar->def;
      return d;
    }
  else
    {
      warnx("El arbol es vacio\n");
    }
  return(d);
}
/*
  Devuelve el data de la raiz del arbol que se le
  pase como argumento.

  PRE: !abb_is_empty(ar)
  POS: Cardamomo
*/

bool
abb_is_empty(abb ar)
{
  /*	printf("el arbol es %p"*/
  return(ar==NULL);
}

abb
abb_insert(abb ar,key k,data d)
{

  abb a;
  abb tmp1;
  abb tmp2;
  char *tchar; /* Para el key que entra como parametro */
  char *trchar; /* Para los sucesivos "root's" del arbol */
  
  
  a=(abb)malloc(sizeof(struct sabb));
  a->pal=key_clone(k);
  a->def=data_clone(d);
  a->left=NULL;
  a->rgt=NULL;
  a->f=NULL;	
  if(abb_is_empty(ar))
    ar=a;

  else
    {/*si el arbol no es vacio*/
      tmp1=ar;
      
      tchar=key_toStr(k); /* Este es el key que entra. Lo hago string,
			     y lo comparo en el while */
      trchar=key_toStr(abb_root_key(tmp1));
      
      /* Nota mental: si son iguales, �NO ENTRA EN EL BUCLE! */
      

      while( !abb_is_empty(tmp1))/* && strcmp(tchar,trchar)!=0)*/
	{
	  tmp2=tmp1; 
	  
	  if(strcmp(trchar,tchar)>0)
	    {
	      tmp1=abb_left(tmp1);
	    }
	  else
	    {
	      tmp1=abb_right(tmp1);	      
	    }

	  if( !abb_is_empty(tmp1) )
	    {
	      free(trchar);
	      trchar=key_toStr(abb_root_key(tmp1));
	    }
	}
      /*
	Si sale porque ya estaba el que queria insertar,
	la funcion no hace nada; si tmp1==NULL al final
	del ciclo, lo inserta como hoja
      */
      if(abb_is_empty(tmp1) )
	{
	  free(trchar);
	  trchar=key_toStr(abb_root_key(tmp2));
	  
	  if(strcmp(trchar,tchar)>0)
	    {
	      tmp2->left=a;
	      a->f=tmp2;
	    }	
	  else
	    {
	      tmp2->rgt=a;
	      a->f=tmp2;
	    }
	}
      free(tchar);
      free(trchar);

    }
  return(ar);
}

data
abb_search(key k,abb ar)
{
  abb p;
  char *tchar; /* Para el key que entra como parametro */
  char *trchar; /* Para los sucesivos "root's" del arbol */
  
  p=ar;
  tchar=key_toStr(k); /* Este es el key que entra. Lo hago string,
			 y lo comparo en el while */
  trchar=key_toStr(abb_root_key(p));
  while( (!abb_is_empty(p) && strcmp(tchar,trchar)!=0) )
    {
      if(strcmp(trchar,tchar)>0)
	p=p->left;
      else
	p=p->rgt;
      if( !abb_is_empty(p) )
	{
	  free(trchar);
	  trchar=key_toStr(abb_root_key(p));
	}
    }
  free(trchar);
  free(tchar);
  
  
  if( !abb_is_empty(p) )
    /* osea, salio porque encontro la palabra */
    return(p->def);
  else
    return(NULL);
}

bool
abb_exist(key k, abb a)
{
  return(abb_search(k,a)!=NULL);
}

abb
abb_destroy(abb ar)
{
  while(!abb_is_empty(ar))
    ar=abb_del(ar,abb_root_key(ar));

  return ar;
}




bool
has_right(abb arbol)
{
  bool b;
  if (arbol!=NULL)
    {
      if (arbol->rgt!=NULL)
	b=TRUE;
      else
	b=FALSE;
    }
  else
    b=FALSE;

  return b;
}

bool
has_left(abb arbol)
{ 
  bool b;
  if (arbol!=NULL)
    {
      if (arbol->left!=NULL)
	b=TRUE;
      else
	b=FALSE;
    }
  else
    b=FALSE;

  return b;
}



bool 
is_hoja(abb arbol)
{
  bool b=FALSE;

  if (arbol->rgt==NULL)
    {
      if(arbol->left==NULL)
	b=TRUE;
    }

  return b;
}/*retorna true si no posee hijo hizquierdo y hijo derecho*/


void
lift(abb ar1, abb ar2)
{
  abb tmp;

  tmp=(abb)malloc(sizeof(struct sabb));
   	
  tmp->pal=ar1->pal;
  tmp->def=ar1->def;
	
  ar1->pal=ar2->pal;
  ar1->def=ar2->def;
	
  ar2->pal=tmp->pal;	
  ar2->def=tmp->def;
	
  free(tmp);
}

abb
hundir(abb ar)
{
  bool b=TRUE;
  char *str1=NULL;
  char *str2=NULL;	
  char *str3=NULL;
  int i;
  abb tmp;
  tmp=ar;
  while(b && !(is_hoja(tmp)))
    {
      str1=key_toStr(abb_root_key(tmp));
      if (has_left(tmp))
	str2=key_toStr(abb_root_key(tmp->left));
      if (has_right(tmp))
	str3=key_toStr(abb_root_key(tmp->rgt));
		
      if (has_left(tmp) && has_right(tmp))
	{
	  i=strcmp(str1,str2);
		
	  if (i<0)
	    {
	      lift(tmp,tmp->left);
	      tmp=tmp->left;
	    }
	  else 
	    {
	      i=strcmp(str1,str3);
	      if (i>0)
		{
		  lift(tmp,tmp->rgt);
		  tmp=tmp->rgt;
		}
	      else
		{
		  b=FALSE;
		}
	    }	
	}
      else if (has_left(tmp)==FALSE)
	{
	  i=strcmp(str1,str3);
	  if (i>0)
	    {
	      lift(tmp,tmp->rgt);
	      tmp=tmp->rgt;
	    }
	  else
	    {
	      b=FALSE;
	    }
	}
      else if(has_right(tmp)==FALSE)
	{	
	  i=strcmp(str1,str2);
	  if (i<0)
	    {
	      lift(tmp,tmp->left);
	      tmp=tmp->left;
	    }
      else
        {
          b=FALSE;
        }
	}
	if (str1 != NULL)
        {
        free(str1);
        str1=NULL;
        }
    if (str2 != NULL)
        {
        free(str2);
        str2=NULL;
        }
    if (str3 != NULL)
        {
        free(str3);
        str3=NULL;
        }
    }
  return ar;

}

abb
abb_max(abb ar)
{
  abb tem;
  if (!abb_is_empty(ar))
    {
      tem=ar;
      if( !abb_is_empty(tem->rgt) )
	{
	  while(!abb_is_empty(tem->rgt))
	    tem=tem->rgt;
	}
      if (!(abb_is_empty(tem->left)))
	{
	  tem=tem->left;
	  tem=abb_max(tem);
	}
    }
  return tem;
}



abb
abb_nododel(abb ar)
{/*elimina el nodo que se encuentra apuntado por ar*/
  if (ar->f!=NULL)
    {
      if ((ar)==(ar->f->rgt))
	ar->f->rgt=NULL;
      else
	ar->f->left=NULL;
    }
  ar->pal=key_destroy(ar->pal);
  ar->def=data_destroy(ar->def);
	
  free(ar);
  ar=NULL;
  return ar;
}

abb
abb_del(abb ar,key k)
{
  abb tmp;
  abb maxhoja;
	
  char *str1;
  char *str2;
  int i;

  tmp=ar;

  str1=key_toStr(abb_root_key(tmp));
  str2=key_toStr(k);
	
  i=strcmp(str1, str2);
	
  /*busco el elemento que deseo eliminar*/
	
  while( (!abb_is_empty(tmp) && i!=0) )
    {
			
      if(i>0)
	tmp=tmp->left;
      else if (i<0)
	tmp=tmp->rgt;
		
      
      if(!(abb_is_empty(tmp)))
	{
	  free(str1);
	  str1=key_toStr(abb_root_key(tmp));
	}
      i=strcmp(str1, str2);
    }
  free(str1);
  free(str2);
  /*encontre el elemento que quiero eliminar, 
    ahora root(tmp)=elemento a eliminar*/	
  if (is_hoja(tmp))
    {/*caso en el que el elemento a eliminar es una hoja*/
      tmp=abb_nododel(tmp);
    }
  else
    {	/*caso que no es una hoja*/
      /*el elemento a eliminar pasa a la posicion de la maxima hoja y viceversa*/
		
      maxhoja=abb_max(tmp);
      lift(maxhoja,tmp);
      /*ahora
	maxhoja=elemento a eliminar
	tmp=elemento a re posicionar*/
      tmp=hundir(tmp);
      maxhoja=abb_nododel(maxhoja);
		
    }

  if((ar->pal)==NULL)
    return NULL;

  return ar;
		
}
